665E - Beautiful Subarrays - CodeForces Solution

#pragma GCC optimize(3)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6+10;
const int M=2*N;
const int mod=998244353;
const double eps = 1e-8;
int n,k;
int tr[N*21][2],idx;
int cnt[N*21];
void insert(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        if(x>>i&1)
        {
            if(tr[p][1]);
            else tr[p][1]=++idx;
            p=tr[p][1];
        }
        else 
        {
            if(tr[p][0]);
            else tr[p][0]=++idx;
            p=tr[p][0];
        }
        cnt[p]++;
    }
}
long long query(int sum)
{
    long long ans=0;
    int p=0;
    for(int i=30;i>=0;i--)
    {
        if(k>>i&1)
        {
            if(sum>>i&1)
            {
                if(tr[p][0])
                {
                    p=tr[p][0];
                }
                else p=0;
            }
            else 
            {
                if(tr[p][1]) p=tr[p][1];
                else p=0;
            }
        }
        else 
        {
            if(sum>>i&1)
            {
                ans+=cnt[tr[p][0]];
                p=tr[p][1];
            }
            else 
            {
                ans+=cnt[tr[p][1]];
                p=tr[p][0];
            }
        }
        if(p==0)break;
    }
    if(p==0) return ans;
    return ans+cnt[p];
}
void slove()
{
    cin >> n>>k;
    insert(0);
    int sum=0;
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin >> x;
        sum^=x;
        ans+=query(sum);
        insert(sum);
    }
    cout << ans<<"\n";
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        slove();
    }
    return 0;
}
//104 106